package problem51;

//51.N皇后
//https://leetcode.cn/problems/n-queens//






import java.util.ArrayList;
import java.util.List;

class Solution {
    List<List<String>> ret = new ArrayList<>();
    List<String> path = new ArrayList<>();
    boolean[] row;
    boolean[] dig1;
    boolean[] dig2;
    int n;
    public List<List<String>> solveNQueens(int _n) {
        n = _n;
        row = new boolean[n];
        dig1 = new boolean[2*n];
        dig2 = new boolean[2*n];
        dfs(0);
        return ret;
    }
    public void dfs(int u) {
        if(u == n) {
            ret.add(new ArrayList(path));
            return;
        }

        StringBuffer s = new StringBuffer();
        for(int i = 0; i<n; i++) {
            s.append(".");
        }

        for(int i = 0; i<n; i++) {
            if(!row[i] && !dig1[i-u+n-1] && !dig2[i+u]) {
                row[i] = dig1[i-u+n-1] = dig2[i+u] = true;
                s.setCharAt(i,'Q');
                path.add(new String(s));
                dfs(u+1);
                //回溯
                row[i] = dig1[i-u+n-1] = dig2[i+u] = false;
                s.setCharAt(i,'.');
                path.remove(path.size()-1);
            }
         }
    }
}